package LeetCode;

public class LC_042_TrappingRainWater {
    public static void main(String[] args) {

    }
    public int trap(int[] height) {
        int length;
        int maxLeftHeight = 0, maxRightHeight = 0;
        int result = 0;
        int temp;

        if (height == null || (length = height.length) == 0)
            return 0;
        int[] leftMaxHeight = new int[length];
        int[] rightMaxHeight = new int[length];

        for (int i = 0; i < length; i++) {
            leftMaxHeight[i] = maxLeftHeight;
            maxLeftHeight = Math.max(maxLeftHeight, height[i]);
        }

        for (int i = length - 1; i >= 0; i--) {
            rightMaxHeight[i] = maxRightHeight;
            maxRightHeight = Math.max(maxRightHeight, height[i]);
        }

        for (int i = 0; i < length; i++) {
            temp = Math.min(leftMaxHeight[i], rightMaxHeight[i]);
            if (temp >= height[i])
                result += temp - height[i];
        }

        return result;
    }
}
